# # -*- coding:utf-8 -*-
# class Solution:
#     def VerifySquenceOfBST(self, s):
#         # write code here
#         length = len(s)
#         if length == 0:
#             return False
#         middle = 0
#         v = s[-1]
#         if min(s) > v or max(s) < v or max(s) == v or min(s) == v:
#             return True
#         for i in range(len(s)):
#
#             if s[i] > v:
#                 middle = i
#                 break
#         for j in range(middle + 1, length - 1):
#             if s[j] < v:
#                 return False
#         left = True
#         if middle > 0:
#             left = self.VerifySquenceOfBST(s[:middle])
#         right = True
#         if middle < length - 1:
#             right = self.VerifySquenceOfBST(s[middle:length - 1])
#         return left and right


# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, s):
        # write code here
        if not s:
            return True
        l = len(s)
        r = s[-1]
        if max(s)<=r or min(s)>=r:
            return True
        for i in range(len(s)-1):
            if s[i] > r:
                b = i
                break
        if s[:b] and s[b+1:l-1] and  r>=max(s[:b]) and r<=min(s[b+1:l-1]):
            return True
        else:
            return False
        if b>0:
            l = self.VerifySquenceOfBST(s[:b])
        if b<l-1:
            r = self.VerifySquenceOfBST(s[b:l-1])
        return  l and r

array3 = [7,4,6,5]
S = Solution()

print(S.VerifySquenceOfBST(array3))